{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Repeated DNA Sequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #hash-table #string #sliding-window #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #哈希表 #字符串 #滑动窗口 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findRepeatedDnaSequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重复的DNA序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>DNA序列</strong>&nbsp;由一系列核苷酸组成，缩写为<meta charset=\"UTF-8\" />&nbsp;<code>'A'</code>,&nbsp;<code>'C'</code>,&nbsp;<code>'G'</code>&nbsp;和<meta charset=\"UTF-8\" />&nbsp;<code>'T'</code>.。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<meta charset=\"UTF-8\" /><code>\"ACGAATTCCG\"</code>&nbsp;是一个 <strong>DNA序列</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>在研究 <strong>DNA</strong> 时，识别 DNA 中的重复序列非常有用。</p>\n",
    "\n",
    "<p>给定一个表示 <strong>DNA序列</strong> 的字符串 <code>s</code> ，返回所有在 DNA 分子中出现不止一次的&nbsp;<strong>长度为&nbsp;<code>10</code></strong>&nbsp;的序列(子字符串)。你可以按 <strong>任意顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT\"\n",
    "<strong>输出：</strong>[\"AAAAACCCCC\",\"CCCCCAAAAA\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"AAAAAAAAAAAAA\"\n",
    "<strong>输出：</strong>[\"AAAAAAAAAA\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code><code>==</code><code>'A'</code>、<code>'C'</code>、<code>'G'</code>&nbsp;or&nbsp;<code>'T'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [repeated-dna-sequences](https://leetcode.cn/problems/repeated-dna-sequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [repeated-dna-sequences](https://leetcode.cn/problems/repeated-dna-sequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT\"', '\"AAAAAAAAAAAAA\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "  def findRepeatedDnaSequences(self, s):\n",
    "    \"\"\"\n",
    "    :type s: str\n",
    "    :rtype: List[str]\n",
    "    \"\"\"\n",
    "    count = defaultdict( int )\n",
    "\n",
    "    for i in range( 0, len( s ) - 9):\n",
    "      count[ s[ i : i + 10 ] ] += 1\n",
    "\n",
    "    return [ seq for seq,c in count.items() if c > 1 ]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        for i in range(n - 9):\n",
    "            s_temp = s[i: i + 10]\n",
    "            if s.find(s_temp, i + 1) != -1:\n",
    "                if s_temp not in stack:\n",
    "                    stack.append(s_temp)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        l = []\n",
    "        output = []\n",
    "        if (len(s) > 10000 or len(s)<=10):\n",
    "            return output\n",
    "        for i in range(len(s)-9):\n",
    "            if s[i:i+10] in l:\n",
    "                output.append(s[i:i+10])\n",
    "            else:\n",
    "                l.append(s[i:i+10])     \n",
    "        return list(set(output))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        if len(s) > 10000:\n",
    "            return []\n",
    "        k = []\n",
    "        res = []\n",
    "        for i in range(len(s)-9): \n",
    "            if s[i:i+10] in k and s[i:i+10] not in res:\n",
    "                res.append(s[i:i+10])\n",
    "            k.append(s[i:i+10])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "#         if len(s) <= 10:\n",
    "#             return []\n",
    "#         index = {\"A\": 0, \"C\": 1, \"G\": 2, \"T\":3}\n",
    "#         val = sum(index[s[i]] << (2*i) for i in range(10))\n",
    "#         n = len(s)\n",
    "#         exist = {val:1}\n",
    "#         ans = []\n",
    "#         for i in range(10, n):\n",
    "#             val = ((val - index[s[i - 10]])>>2) + (index[s[i]] << 18)\n",
    "#             if val in exist:\n",
    "#                 exist[val] == 1 and ans.append(s[i-9:i+1])\n",
    "#                 exist[val] += 1\n",
    "#             else:\n",
    "#                 exist[val] = 1\n",
    "#         return ans\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        if len(s)>=100000:\n",
    "            return []\n",
    "        se=[]\n",
    "        h=defaultdict(int)\n",
    "        for i in range(len(s)-9):\n",
    "            c=s[i:i+10]\n",
    "            h[c]+=1\n",
    "            if h[c]==2:\n",
    "                se.append(c)\n",
    "        return se\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        if len(s)>=100000:\n",
    "            return []\n",
    "        se=[]\n",
    "        h=defaultdict(int)\n",
    "        for i in range(len(s)-9):\n",
    "            c=s[i:i+10]\n",
    "            h[c]+=1\n",
    "            if h[c]==2:\n",
    "                se.append(c)\n",
    "        return se"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        l=len(s)\n",
    "        t=[]\n",
    "        if l<=10:\n",
    "            return t\n",
    "        d={'A':0,'C':1,'G':2,'T':3}\n",
    "        a=0\n",
    "        for i in range(10):\n",
    "            a<<=2\n",
    "            a+=d[s[i]]\n",
    "        r=[a]*(l-9)\n",
    "        for i in range(l-10):\n",
    "            a&=262143\n",
    "            a<<=2\n",
    "            a+=d[s[i+10]]\n",
    "            r[i]=a\n",
    "        r.sort()\n",
    "        i=1\n",
    "        while i<l-9:\n",
    "            if r[i]==r[i-1]:\n",
    "                a=r[i]\n",
    "                t.append(ns(a))\n",
    "                i+=1\n",
    "                while i<l-9 and r[i]==a:\n",
    "                    i+=1\n",
    "            else:\n",
    "                i+=1\n",
    "        return t\n",
    "\n",
    "def ns(n):\n",
    "    p=['A','C','G','T']\n",
    "    r=['A']*10\n",
    "    for i in range(10):\n",
    "        a=n&3\n",
    "        r[9-i]=p[a]\n",
    "        n>>=2\n",
    "    return ''.join(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        l, p, ret = len(s), set(), set()\n",
    "        # print(dat)\n",
    "        for d in (\"A\", \"G\", \"C\", \"T\"):\n",
    "            pos = s.find(d)\n",
    "            # print(f\"pos {pos} for {d}\")\n",
    "            while pos > -1:\n",
    "                if pos + 10 <= l:\n",
    "                    t = s[pos: pos + 10]\n",
    "                    if t in p:\n",
    "                        ret.add(t)\n",
    "                    p.add(t)\n",
    "                else:\n",
    "                    break\n",
    "                pos = s.find(d, pos + 1)\n",
    "            p.clear()\n",
    "        return list(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: 'str') -> 'List[str]':\n",
    "        l=set()\n",
    "        n=set()\n",
    "        for i in range(len(s)-9):\n",
    "            j = s[i:i+10]\n",
    "            if j in l:\n",
    "                n.add(j)\n",
    "            else:\n",
    "                l.add(j)\n",
    "        return list(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        wordset, res, count = set(),set(), len(s)\n",
    "        i = 0\n",
    "        while i + 10 <= count:\n",
    "            if s[i:i + 10] in wordset:\n",
    "                res.add(s[i:i + 10])\n",
    "            else:\n",
    "                wordset.add(s[i:i + 10])\n",
    "            i += 1\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        if len(s)<10:\n",
    "            return []\n",
    "        else:\n",
    "            res = []\n",
    "            appeared = {}\n",
    "            mask = 0x7ffffff\n",
    "            cur = 0\n",
    "            for i in range(9):\n",
    "                cur = (cur<<3) | (ord(s[i])&7)\n",
    "            for i in range(9,len(s)):\n",
    "                cur = (cur&mask)<<3 | (ord(s[i])&7)\n",
    "                if cur not in appeared:\n",
    "                    appeared[cur] = 1\n",
    "                else:\n",
    "                    if appeared[cur] == 1:\n",
    "                        res.append(s[i-9:i+1])\n",
    "                    appeared[cur] += 1\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str):\n",
    "        def compare(index_list, step, ns):\n",
    "            n = len(index_list)\n",
    "            index_dict = defaultdict(list)\n",
    "            for i in index_list:\n",
    "                if i + step < ns:\n",
    "                    key = s[i + step]\n",
    "                    index_dict[key].append(i)\n",
    "\n",
    "            res = []\n",
    "            for key, val in index_dict.items():\n",
    "                if step == 9:\n",
    "                    if len(val) >= 2:\n",
    "                        res += val\n",
    "                if len(val) == 2:\n",
    "                    ind1 = val[0]\n",
    "                    ind2 = val[1]\n",
    "                    if s[ind1 + step + 1: ind1 + 10] == s[ind2 + step + 1: ind2 + 10]:\n",
    "                        res.append(ind1)\n",
    "                elif len(val) == 1:\n",
    "                    continue\n",
    "                else:\n",
    "                    res += compare(val, step + 1, ns)\n",
    "            return res\n",
    "\n",
    "        n = len(s)\n",
    "        if n < 10:\n",
    "            return []\n",
    "        res_list = compare(list(range(n - 9)), 0, n)\n",
    "        final_res = []\n",
    "        for i in res_list:\n",
    "            final_res.append(s[i: i + 10])\n",
    "        return list(set(final_res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str):\n",
    "        def compare(index_list, step, ns):\n",
    "            n = len(index_list)\n",
    "            index_dict = defaultdict(list)\n",
    "            for i in index_list:\n",
    "                if i + step < ns:\n",
    "                    key = s[i + step]\n",
    "                    index_dict[key].append(i)\n",
    "\n",
    "            res = []\n",
    "            for key, val in index_dict.items():\n",
    "                if step == 9:\n",
    "                    if len(val) >= 2:\n",
    "                        res += val\n",
    "                if len(val) == 2:\n",
    "                    ind1 = val[0]\n",
    "                    ind2 = val[1]\n",
    "                    if s[ind1 + step + 1: ind1 + 10] == s[ind2 + step + 1: ind2 + 10]:\n",
    "                        res.append(ind1)\n",
    "                elif len(val) == 1:\n",
    "                    continue\n",
    "                else:\n",
    "                    res += compare(val, step + 1, ns)\n",
    "            return res\n",
    "\n",
    "        n = len(s)\n",
    "        if n < 10:\n",
    "            return []\n",
    "        res_list = compare(list(range(n - 9)), 0, n)\n",
    "        final_res = []\n",
    "        for i in res_list:\n",
    "            final_res.append(s[i: i + 10])\n",
    "        return list(set(final_res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        if len(s) < 11:\n",
    "            return []\n",
    "\n",
    "        last = {\n",
    "            'A': None,\n",
    "            'T': None,\n",
    "            'C': None,\n",
    "            'G': None,\n",
    "        }\n",
    "        prev = []\n",
    "        for i in range(len(s)):\n",
    "            prev.append(last[s[i]])\n",
    "            last[s[i]] = i\n",
    "\n",
    "        for n in range(1, 10):\n",
    "            nextc = [s[i+n] for i in range(len(s)-n)] + [None] * n\n",
    "            for i in range(len(s)-10, -1, -1):\n",
    "                j = prev[i]\n",
    "                while j is not None and nextc[i] != nextc[j]:\n",
    "                    j = prev[j]\n",
    "                prev[i] = j\n",
    "\n",
    "        count = [1] * len(s)\n",
    "        for i in range(len(s)-10,-1,-1):\n",
    "            if prev[i] is not None:\n",
    "                count[prev[i]] += count[i]\n",
    "                count[i] = 0\n",
    "\n",
    "        return [s[i:i+10] for i in range(len(s)) if count[i] > 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def findRepeatedDnaSequences1(s):\n",
    "    n = len(s)\n",
    "    m = set()\n",
    "    ans = set()\n",
    "    for i in range(n-9):\n",
    "        if s[i:i+10] in m:\n",
    "            ans.add(s[i:i+10])\n",
    "        else:\n",
    "            m.add(s[i:i+10])\n",
    "    return list(ans)\n",
    "\n",
    "def findRepeatedDnaSequences2(s):\n",
    "    n = len(s)\n",
    "    if n <= 10:\n",
    "        return []\n",
    "    \n",
    "    m = set()\n",
    "    ans = set()\n",
    "    key = 0\n",
    "    # 初始化前十位字母\n",
    "    for i in range(10):\n",
    "        key <<= 3\n",
    "        key |= (ord(s[i])&7)\n",
    "    m.add(key)\n",
    "    \n",
    "    for i in range(10, n):\n",
    "        key <<= 3\n",
    "        key |= (ord(s[i])&7)\n",
    "        key &= 0x3fffffff\n",
    "        if key in m:\n",
    "            ans.add(s[i-9:i+1])\n",
    "        else:\n",
    "            m.add(key)\n",
    "            \n",
    "    return list(ans)\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        return findRepeatedDnaSequences2(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        length = len(s)\n",
    "        if length <= 10:\n",
    "            return []\n",
    "        else:\n",
    "            # from sortedcontainer import SortedList\n",
    "            n = 0\n",
    "            strlist = []\n",
    "            re = set()\n",
    "            for n in range(length-9):\n",
    "                strlist.append(s[n:n+10])\n",
    "                n += 1\n",
    "            # strlist = SortedList(strlist)\n",
    "            strlist.sort()\n",
    "            n = 0\n",
    "            length = len(strlist)\n",
    "            for n in range(length-1):\n",
    "                if strlist[n] == strlist[n+1]:\n",
    "                    re.add(strlist[n])\n",
    "                    n += 2\n",
    "                else:\n",
    "                    n += 1\n",
    "            else:\n",
    "                return list(re)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        length = len(s)\n",
    "        if length <= 10:\n",
    "            return []\n",
    "        re = []\n",
    "        li = [[]for i in range(1000)]\n",
    "        for i in range(length-9):\n",
    "            obj = s[i:i+10]\n",
    "            n = hash(obj)%1000\n",
    "            if li[n] == []:\n",
    "                li[n].append(obj)\n",
    "            elif obj not in li[n]:\n",
    "                li[n].append(obj)\n",
    "            elif obj not in re:\n",
    "                re.append(obj)\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        length = len(s)\n",
    "        if length <= 10:\n",
    "            return []\n",
    "        re = []\n",
    "        li = [[]for i in range(10000)]\n",
    "        for i in range(length-9):\n",
    "            obj = s[i:i+10]\n",
    "            n = hash(obj)%10000\n",
    "            if li[n] == []:\n",
    "                li[n].append(obj)\n",
    "            elif obj not in li[n]:\n",
    "                li[n].append(obj)\n",
    "            elif obj not in re:\n",
    "                re.append(obj)\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        dic5 = {}\n",
    "        res = []\n",
    "        if len(s) <= 10:\n",
    "            return []\n",
    "        for i in range(len(s) - 4):\n",
    "            if s[i:i+5] in dic5:\n",
    "                dic5[s[i:i+5]].append(i)\n",
    "            else:\n",
    "                dic5[s[i:i+5]] = [i]\n",
    "\n",
    "        popkey = []\n",
    "\n",
    "        for key in dic5:\n",
    "            if len(dic5[key]) < 2:\n",
    "                popkey.append(key)\n",
    "\n",
    "        for key in popkey:\n",
    "            dic5.pop(key)\n",
    "\n",
    "\n",
    "        dic2 = [''] * (len(s))\n",
    "                \n",
    "        for key, value in dic5.items():\n",
    "            for v in value:\n",
    "                dic2[v] = key\n",
    "        \n",
    "        print(dic5)\n",
    "        print(dic2)\n",
    "        \n",
    "        for i in range(len(dic2) - 5):\n",
    "            if dic2[i] == '' or dic2[i + 5] == '':\n",
    "                continue\n",
    "            s1 = dic2[i]\n",
    "            s2 = dic2[i + 5]\n",
    "            if s1 + s2 in res:\n",
    "                continue\n",
    "            for jp in dic5[s1][::-1]:\n",
    "                if jp <= i:\n",
    "                    break\n",
    "                if jp >= len(s) - 5:\n",
    "                    continue\n",
    "                if dic2[jp + 5] == s2:\n",
    "                    res.append(s1 + s2)\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        suffix = []\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            suffix.append(s[i:i+10])\n",
    "        suffix.sort()\n",
    "        rtn = []\n",
    "        last = suffix[0]\n",
    "        # print(suffix)\n",
    "        for i in range(1,n):\n",
    "            j = 0\n",
    "            if suffix[i] == last and last not in rtn:\n",
    "                rtn.append(last)\n",
    "            last = suffix[i]\n",
    "        return rtn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        d = {'A':0, 'C':1, 'G':2, 'T':3}\n",
    "        res = set()\n",
    "        seen = set()\n",
    "        l, r, base, cur_hash, n = 0, 0, 4, 0, int(pow(4,9))\n",
    "        while r < len(s):\n",
    "            cur_hash = cur_hash * base + d[s[r]]\n",
    "            r += 1\n",
    "            while r-l >= 10:\n",
    "                if cur_hash in seen:\n",
    "                    res.add(s[l:r])\n",
    "                seen.add(cur_hash)\n",
    "                cur_hash -= d[s[l]] * n\n",
    "                l += 1\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        if len(s) < 10:\n",
    "            return []\n",
    "        hashTable = [0 for i in range(4 ** 10)]\n",
    "        a = {'AA': 0, 'AC': 1, 'AG': 2, 'AT': 3,\n",
    "             'CA': 4, 'CC': 5, 'CG': 6, 'CT': 7,\n",
    "             'GA': 8, 'GC': 9, 'GG': 10, 'GT': 11,\n",
    "             'TA': 12, 'TC': 13, 'TG': 14, 'TT': 15}\n",
    "        result = []\n",
    "        for i in range(len(s) - 9):\n",
    "            p = s[i : i + 10]\n",
    "            index = 4 ** 8 * a[p[0:2]] + 4 ** 6 * a[p[2:4]] + 4 ** 4 * a[p[4:6]] + 4 ** 2 * a[p[6:8]] + a[p[8:10]]\n",
    "            hashTable[index] += 1\n",
    "            if hashTable[index] == 2:\n",
    "                result.append(p)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        dic = {'A': 0, 'G': 1, 'C': 2, 'T': 3}\n",
    "        nums = list(map(lambda x: dic.get(x), s))\n",
    "\n",
    "        left, right = 0, 0\n",
    "        winHash = 0\n",
    "        seen = set()\n",
    "        res = set()\n",
    "        R = 4\n",
    "        L = 10\n",
    "        RL = R ** (L - 1)\n",
    "        while right < len(nums):\n",
    "            winHash = winHash * R + nums[right]\n",
    "            right += 1\n",
    "            if right - left == L:\n",
    "                if winHash in seen:\n",
    "                    res.add(s[left:right])\n",
    "                else:\n",
    "                    seen.add(winHash)\n",
    "                winHash -= nums[left] * RL\n",
    "                left += 1\n",
    "        return list(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        lens = len(s)\n",
    "        if lens <= 10: return []\n",
    "        \n",
    "        states, results = set(), set()\n",
    "        \n",
    "        x = self.encode(s[: 10])\n",
    "        states.add(x)\n",
    "        M = 2**20\n",
    "        for i in range(10, lens):\n",
    "            x = ((x<<2)%M)+self.encode(s[i])\n",
    "            if x in states:\n",
    "                results.add(s[i-10+1: i+1])\n",
    "            else:\n",
    "                states.add(x)\n",
    "        \n",
    "        return list(results)\n",
    "        \n",
    "    def encode(self, s):\n",
    "        lens = len(s)\n",
    "        c = s[0]\n",
    "        if c == \"A\": i = 0b00\n",
    "        if c == \"C\": i = 0b01\n",
    "        if c == \"G\": i = 0b10\n",
    "        if c == \"T\": i = 0b11\n",
    "        if lens == 1: return i\n",
    "        return (i<<(2*(lens-1)))+self.encode(s[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        GENE_LENGTH = 10\n",
    "        vals = {'A': 0, 'C': 1, 'G': 2, 'T': 3}\n",
    "        MASK = (1 << 20) - 1\n",
    "        n = len(s)\n",
    "        if n <= GENE_LENGTH:\n",
    "            return []\n",
    "        has = set()\n",
    "        ans = set()\n",
    "        val = 0\n",
    "        for c in s[: GENE_LENGTH - 1]:\n",
    "            val = val << 2 | vals[c]\n",
    "        for i, c in enumerate(s[GENE_LENGTH - 1:]):\n",
    "            val = (val << 2 | vals[c]) & MASK\n",
    "            if val in has:\n",
    "                ans .add(s[i: i + GENE_LENGTH])\n",
    "            else:\n",
    "                has.add(val)\n",
    "        return list(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        nums = [0] * len(s)\n",
    "        for i in range(len(nums)):\n",
    "            if s[i] == 'A':\n",
    "                nums[i] = 0\n",
    "            elif s[i] == 'G':\n",
    "                nums[i] = 1\n",
    "            elif s[i] == 'C':\n",
    "                nums[i] = 2\n",
    "            elif s[i] == 'T':\n",
    "                nums[i] = 3\n",
    "\n",
    "        # 记录重复出现的哈希值\n",
    "        seen = set()\n",
    "        # 记录重复出现的字符串结果\n",
    "        res = set()\n",
    "\n",
    "        # 数字位数\n",
    "        L = 10\n",
    "        # 进制\n",
    "        R = 4\n",
    "        # 存储 R^(L - 1) 的结果\n",
    "        RL = R ** (L - 1)\n",
    "        # 维护滑动窗口中字符串的哈希值\n",
    "        windowHash = 0\n",
    "\n",
    "        # 滑动窗口代码框架，时间 O(N)\n",
    "        left, right = 0, 0\n",
    "        while right < len(nums):\n",
    "            # 扩大窗口，移入字符，并维护窗口哈希值（在最低位添加数字）\n",
    "            windowHash = R * windowHash + nums[right]\n",
    "            right += 1\n",
    "\n",
    "            # 当子串的长度达到要求\n",
    "            if right - left == L:\n",
    "                # 根据哈希值判断是否曾经出现过相同的子串\n",
    "                if windowHash in seen:\n",
    "                    # 当前窗口中的子串是重复出现的\n",
    "                    res.add(s[left:right])\n",
    "                else:\n",
    "                    # 当前窗口中的子串之前没有出现过，记下来\n",
    "                    seen.add(windowHash)\n",
    "                # 缩小窗口，移出字符，并维护窗口哈希值（删除最高位数字）\n",
    "                windowHash -= nums[left] * RL\n",
    "                left += 1\n",
    "\n",
    "        # 转化成题目要求的 List 类型\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        nums = [0] * len(s)\n",
    "        for i in range(len(nums)):\n",
    "            if s[i] == 'A':\n",
    "                nums[i] = 0\n",
    "            elif s[i] == 'G':\n",
    "                nums[i] = 1\n",
    "            elif s[i] == 'C':\n",
    "                nums[i] = 2\n",
    "            elif s[i] == 'T':\n",
    "                nums[i] = 3\n",
    "\n",
    "        # 记录重复出现的哈希值\n",
    "        seen = set()\n",
    "        # 记录重复出现的字符串结果\n",
    "        res = set()\n",
    "\n",
    "        # 数字位数\n",
    "        L = 10\n",
    "        # 进制\n",
    "        R = 4\n",
    "        # 存储 R^(L - 1) 的结果\n",
    "        RL = R ** (L - 1)\n",
    "        # 维护滑动窗口中字符串的哈希值\n",
    "        windowHash = 0\n",
    "\n",
    "        # 滑动窗口代码框架，时间 O(N)\n",
    "        left, right = 0, 0\n",
    "        while right < len(nums):\n",
    "            # 扩大窗口，移入字符，并维护窗口哈希值（在最低位添加数字）\n",
    "            windowHash = R * windowHash + nums[right]\n",
    "            right += 1\n",
    "\n",
    "            # 当子串的长度达到要求\n",
    "            if right - left == L:\n",
    "                # 根据哈希值判断是否曾经出现过相同的子串\n",
    "                if windowHash in seen:\n",
    "                    # 当前窗口中的子串是重复出现的\n",
    "                    res.add(s[left:right])\n",
    "                else:\n",
    "                    # 当前窗口中的子串之前没有出现过，记下来\n",
    "                    seen.add(windowHash)\n",
    "                # 缩小窗口，移出字符，并维护窗口哈希值（删除最高位数字）\n",
    "                windowHash -= nums[left] * RL\n",
    "                left += 1\n",
    "\n",
    "        # 转化成题目要求的 List 类型\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        L = 10\n",
    "        bin = {'A':0, 'C':1, 'G':2, 'T':3 }\n",
    "        n = len(s)\n",
    "        if n <= L:\n",
    "            return []\n",
    "        ans = []\n",
    "        x = 0\n",
    "        for ch in s[:L - 1]:\n",
    "            x = (x << 2) | bin[ch]\n",
    "        cnt = defaultdict(int)\n",
    "        for i in range(n - L + 1):\n",
    "            x = ( x << 2 | bin[s[i+L-1]] ) & ( (1 << (L*2)) - 1 )\n",
    "            cnt[x] += 1\n",
    "            if cnt[x] == 2:\n",
    "                ans.append(s[i:i+L])\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        if len(s) < 10:\n",
    "            return []\n",
    "\n",
    "        val = 0\n",
    "        mm = {'A':0, 'C':1, 'G':2, 'T':3};\n",
    "        for i in range(10):\n",
    "            val = val*10 + mm[s[i]]\n",
    "\n",
    "        ss = {}\n",
    "        ss[val] = 1\n",
    "\n",
    "        ans = []\n",
    "        for i in range(10, len(s)):\n",
    "            val = val* 10 + mm[s[i]]\n",
    "            val %= 10**10\n",
    "\n",
    "            if val in ss:\n",
    "                if ss[val] == 1:\n",
    "                    ans.append(s[i-10+1:i+1])\n",
    "                ss[val] += 1\n",
    "            else:\n",
    "                ss[val] = 1\n",
    "\n",
    "\n",
    "\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findRepeatedDnaSequences(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        nums = [0]*len(s)\n",
    "        for i in range(len(nums)):\n",
    "            if s[i] == 'A':\n",
    "                nums[i] = 0\n",
    "            if s[i] == 'C':\n",
    "                nums[i] = 1\n",
    "            if s[i] == 'G':\n",
    "                nums[i] = 2\n",
    "            if s[i] == 'T':\n",
    "                nums[i] = 3\n",
    "        left, right = 0, 0\n",
    "        needs = set()\n",
    "        res = set()\n",
    "        L = 10\n",
    "        R = 10\n",
    "        RL = 10**(L-1)\n",
    "        window_hashcode = 0\n",
    "        while right < len(nums):\n",
    "            window_hashcode = R*window_hashcode + nums[right]\n",
    "            right += 1\n",
    "            while right - left >= L:\n",
    "\n",
    "                if window_hashcode in needs:\n",
    "                    res.add(s[left: right])\n",
    "                else:\n",
    "                    needs.add(window_hashcode)\n",
    "                window_hashcode -= nums[left]*RL\n",
    "                left += 1\n",
    "        return list(res)                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        cache = set()\n",
    "        res = []\n",
    "        for i in range(0, len(s) - 9):\n",
    "            if (t:=s[i:i+10]) in cache:\n",
    "                if t not in res:\n",
    "                    res.append(t)\n",
    "            else:\n",
    "                cache.add(t)\n",
    "            # print(f\"t: {t}\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "\n",
    "        bin_maps = {'A': 1, 'C': 2, 'G': 3, 'T': 0}\n",
    "\n",
    "        def hash(s: str, start: int,  end: int) -> int:\n",
    "            h = 0\n",
    "            for i in range(start, end):\n",
    "                h = 31 * h + bin_maps[s[i]]\n",
    "            return h\n",
    "\n",
    "        cnt = Counter()\n",
    "        ans = []\n",
    "\n",
    "        for e in range(10, n + 1):\n",
    "            h = hash(s, e - 10, e)\n",
    "            cnt[h] += 1\n",
    "            if cnt[h] == 2:\n",
    "                ans.append(s[e-10:e])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        count = [0 for _ in range(len(s))]\n",
    "        set1 = set()\n",
    "        set2 = set()\n",
    "        for i in range(len(s)-9):\n",
    "            if i + 9 < len(s):\n",
    "                if s[i:i+10] in set1:\n",
    "                    count[i] += 1\n",
    "                    set2.add(s[i:i+10])\n",
    "                else:\n",
    "                    set1.add(s[i:i+10])\n",
    "        return list(set2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        L = 10\n",
    "        cnt = defaultdict(int)\n",
    "        for i in range(len(s)-L+1):\n",
    "            sub = s[i : i + L]\n",
    "            cnt[sub] += 1\n",
    "            if cnt[sub] == 2:\n",
    "                ans.append(sub)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
    "        dic = {}\n",
    "        sol = []\n",
    "        for i in range(0,len(s) - 9):\n",
    "            curr = s[i:i+10]\n",
    "            if curr in dic:\n",
    "                dic[curr] += 1\n",
    "            else:\n",
    "                dic[curr] = 1\n",
    "        for x in dic:\n",
    "            if dic[x] > 1:\n",
    "                sol.append(x)\n",
    "        return sol"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
